#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// 最容易理解的递归处理
int max_value(vector<vector<int>>& a,int r,int c)
{
    //为了避免二维矩阵无数据出错
    assert(a.size()>0);
    int Row = a.size();
    int Col = a[0].size();
    if(r == Row-1)
        return a[r][c];
    else
        return max_value(a,r+1,c)+max(a[r+1][c],a[r+1][c+1]);
}
// 使用原数据存储和找到最大和
int max_value1(vector<vector<int>>& a,int r, int c){
    assert(a.size()>0);
    int Row = a.size();
    int Col = a[0].size();
    for(int r = Row-2;r>=0;r--)//-2是为了防止r+1溢出
    {
        for(int c=0;c<Col-1;c++)
            a[r][c] = a[r][c]+max(a[r+1][c],a[r+1][c+1]);
    }
    return a[0][0];
}
int main()
{
    vector<vector<int>>a = {{7,0,0,0,0},
                            {3,8,0,0,0},
                            {8,1,0,0,0},
                            {2,7,4,4,0},
                            {2,5,2,6,5}};
    cout<<max_value1(a,0,0)<<endl;
}
